문서의 임의 삭제는 제재 대상으로, 문서를 삭제하려면 삭제 토론을 진행해야 합니다. 문서 보기문서 삭제토론 튜링 머신 (문단 편집) == 컴퓨터와 튜링 머신 == 현대의 [[폰 노이만 구조]]로 된 컴퓨터는 모두 보편 튜링 머신 이론에 바탕을 두고 있다. 따라서 보편 튜링 머신은 현대의 모든 컴퓨터의 동작을 포함하는 큰 집합이다. 코드 메모리와 데이터 메모리가 분리되어있는 하버드 구조는 테이프를 두 개 달아놓은 튜링 머신이라고 생각할 수 있으니 보편 튜링 머신은 하버드 구조의 컴퓨터도 완벽하게 흉내낼 수 있다. 이로 인하여 컴퓨터의 작업을 이론적으로 모델링할 때는 모두 튜링 머신 이론을 활용한다. 다만 현실의 컴퓨터와 튜링 머신에 약간의 차이점은 있는데, 튜링 머신은 메모리 임의 접근을 상정하지 않고 있다. 다시 말해 테이프의 아무 위치나 원하면 바로 접근할 수는 없다. [[이진 탐색]] 같은 알고리즘의 [[점근 표기법#s-3|시간복잡도]]는 임의 접근이 가능하다면 O(''lg''N) 시간 안에 끝나지만 튜링 머신에서는 훨씬 더 느린 O(N)의 속도를 보인다. 물론 이것은 접근 방식의 차이이지 튜링 머신도 유한한 행동 안에 그 접근을 똑같이 따라할 수 있으므로 기능적으론 동일하다. 현실의 모든 컴퓨터는 엄밀히 따지면 '튜링 완전'하지 않은데, 그 이유는 '''기억장치가 유한하기 때문'''이다. 튜링 머신의 테이프는 무한한 길이를 가져야 하는데 현실의 컴퓨터는 무한한 데이터를 보관할 수 없다. 다만 그렇다고 해서 컴퓨터들이 보편 튜링 머신을 무시한 것은 아니다. [[이상 기체]]는 현실에 없지만 이를 기반으로 한 [[이상 기체 법칙]]은 충분히 활용되는 것처럼 현실의 컴퓨터도 튜링 머신을 기반으로 설계되었기 때문에 유한한 작업을 수행함에 있어 그 이론을 충실히 따르고 있다. 따라서 기억장치가 유한하지만 튜링 완전성을 따르고 있다는 것을 일컬어 '느슨한 튜링 완전성(Loose Turing Completeness)'이라고 한다. 대부분의 컴퓨터는 '느슨한 튜링 완전'이다. 그렇기 때문에 어떤 컴퓨터가 할 수 있는 모든 일은 [[니트로 박사|'충분한' 시간과 메모리만 주어진다면]] 다른 어떤 간단한 컴퓨터로도 할 수 있다. 여러분의 컴퓨터는 슈퍼컴퓨터와 다르지 않다. 다만 그보다 느리고 용량이 작을 뿐이다. 인터넷을 보면 [[마인크래프트]] [[레드스톤]]이나 [[롤러코스터 타이쿤]] 같은 게임으로 '컴퓨터'를 구현했다고 하는 글이나 영상을 종종 볼 수 있다. 이는 해당 게임들의 인게임 요소를 가지고 튜링 완전성을 따르는 장치를 구현한 것이다. 따라서 매우 비효율적이지만 컴퓨터와 마찬가지로 '느슨한 튜링 완전'이기 때문에 컴퓨터가 할 수 있는 일을 똑같이 할 수 있다. 마인크래프트로 계산기를 구현했다거나 하는 것들은 다 이런 뜻이다. 심지어 '''[[TCG]]'''인 [[매직 더 개더링]]으로 [[https://arxiv.org/abs/1904.09828|튜링 머신을 구현]]한 경우도 있다. 논문의 저자들은 60장의 적법한 [[레거시(매직 더 개더링)|레가시]] 포맷 덱으로 튜링 머신을 시뮬레이션하고 승리 조건을 [[정지 문제]]와 동치시킴으로서 최적의 플레이를 계산하는 알고리즘이 존재하지 않는다는 것을 증명했다.저장 버튼을 클릭하면 당신이 기여한 내용을 CC-BY-NC-SA 2.0 KR으로 배포하고,기여한 문서에 대한 하이퍼링크나 URL을 이용하여 저작자 표시를 하는 것으로 충분하다는 데 동의하는 것입니다.이 동의는 철회할 수 없습니다.캡챠저장미리보기